"""
二叉树
"""


class Node:
    """节点类"""
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        return (f'data: {self.val} -- left:{self.left == None}, right:{self.right == None}')


class Tree:
    """
    树类
    """

    def __init__(self, root=None):
        self._root = root

    def is_empty(self):
        return self._root == None

    def insert(self, root, val):
        """
        二叉搜索树插入操作
        """
        if root is None:
            root = Node(val)
        elif val < root.val:
            root.left = self.insert(root.left, val)
        elif val > root.val:
            root.right = self.insert(root.right, val)
        return root

    def add(self, item):
        node = Node(item)
        if not self._root:
            self._root = node
            return
        queue = [self._root]
        while queue:
            cur = queue.pop(0)
            if not cur.left:
                cur.left = node
                return
            elif not cur.right:
                cur.right = node
                return
            else:
                queue.append(cur.left)
                queue.append(cur.right)

    def BFS(self, root, _n=False):
        """
        广度优先
        """
        if root is None:
            return
        # queue队列，保存节点
        queue = []
        # res保存节点值，作为结果
        vals = []
        queue.append(root)
    
        while queue:
            # 拿出队首节点
            currentNode = queue.pop(0)

            vals.append(currentNode.val)
            print(currentNode.val, end=' ')
            if currentNode.left:
                queue.append(currentNode.left)
            if currentNode.right:
                queue.append(currentNode.right)
            else:
                # 每层最后一个时, 换行
                if _n:
                    print()
        return vals

    def query(self, root, val):
        """
        二叉搜索树查询操作
        """
        if root is None:
            return False
        if root.val == val:
            return True
        elif val < root.val:
            return self.query(root.left, val)
        elif val > root.val:
            return self.query(root.right, val)


if __name__ == '__main__':
    node = Node(1)
    tree = Tree(node)

    for i in range(10):
        # tree.insert(tree._root, i)
        tree.add(i)

    tree.BFS(tree._root, True)

    # tree.query(tree._root, 2)

    1